Next Greater Element

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
nums1[0] = 4, nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
nums1[1] = 1, nums2 = [1,3,4,2]. The next greater element is 3.
nums1[2] = 2, nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
nums1[0] = 2, nums2 = [1,2,3,4]. The next greater element is 3.
nums1[1] = 4, nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Constraints:

• 1 <= nums1.length <= nums2.length <= 1000

• 0 <= nums1[i], nums2[i] <= 10^4

• All integers in nums1 and nums2 are unique.

• All the integers of nums1 also appear in nums2.

My Solution

We can solve this problem by scanning the nums2 array from left to right and using a stack to keep track of all the elements for which we have not found the next greater element. We know that all elements on the stack will be in increasing order (from the top of the stack down), so for each element in the array we try to see if the current element is greater than the element on the top of the stack. If it is, we have found the "next greater element" for the element on the top of the stack so we add the mapping from the element on the top of the stack to the next greater element in our HashMap. We continue to pop off the elements from the stack and add these mappings until the stack is empty or the current element is smaller than the top of the stack. At this point we push the current element onto the stack because we haven't found the next greater element for it yet. Once we have iterated through the array, all the elements that are still on the stack are elements that we didn't find the next greater element for, so for all these elements we simply add a mapping to -1 as stated by the problem statement. Finally, we add all the "next greater" elements of nums1 to the output array by accessing our HashMap.

I will illustrate this approach with an example. Suppose we have the following arrays:

nums1: [3,4,0]
nums2: [3,1,2,4,5,0]

We first start scanning the nums2 array from left to right:

[3,1,2,4,5,0]

i : 0
nums2[i] : 3
stack : empty
map : empty

Since the stack is empty, we proceed to add 3 to the stack since we haven't found the next greater element for it yet. We move onto the next element.

[3,1,2,4,5,0]

i : 1
nums2[i] : 1
stack : 3
map: empty

We check to see if the current element 1 is greater than the element on the top of the stack 3. It isn't, so we push the current element 1 onto the stack.

[3,1,2,4,5,0]

i : 2
nums2[i] : 2
stack : 1 3
map: empty

The top of the stack is 1 and the current element is 2, so we have found the next greater element for 1. We create a mapping from 1 -> 2 and pop 1 off the stack.

[3,1,2,4,5,0]

i : 2
nums2[i] : 2
stack : 3
map: (1 -> 2)

The element on the top of the stack is 3 and the current element is 2, so we still haven't found the next greater element for 3. We push 2 onto the stack and move forward.

[3,1,2,4,5,0]

i : 3
nums2[i] : 4
stack : 2 3
map : (1 -> 2)

We check to see if the current element on the stack 4 is greater than the element on the top of the stack: 2. It is, so we add a mapping 2 -> 4 in our HashMap and pop 2 off the stack.

[3,1,2,4,5,0]

i : 3
nums2[i] : 4
stack : 3
map : (1 -> 2), (2 -> 4)

The current element 4 is greater than the element on the top of the stack 3, so we create a mapping from 3 -> 4 and pop 3 from the stack.

[3,1,2,4,5,0]

i : 3
nums2[i] : 4
stack : empty
map : (1 -> 2), (2 -> 4), (3 -> 4)

The stack is empty, so we push 4 onto the stack and continue:

[3,1,2,4,5,0]

i : 4
nums2[i] : 5
stack : 4
map : (1 -> 2), (2 -> 4), (3 -> 4)

We check to see if the current element 5 is greater than the element on top of the stack 4 and it is, so we create a mapping 4 -> 5 and pop 4 off the stack.

[3,1,2,4,5,0]

i : 4
nums2[i] : 5
stack : empty
map : (1 -> 2), (2 -> 4), (3 -> 4), (4 -> 5)

The stack is empty, so we push 5 onto the stack and continue.

[3,1,2,4,5,0]

i : 4
nums2[i] : 0
stack : 5
map : (1 -> 2), (2 -> 4), (3 -> 4), (4 -> 5)

We check to see if the current element 0 is greater than the element on the top of the stack 5 and it isn't, so we simply push 0 onto the stack.

[3,1,2,4,5,0]

i : 4
nums2[i] : end
stack : 0 5
map : (1 -> 2), (2 -> 4), (3 -> 4), (4 -> 5)

At this point we have reached the end of the array, so all the elements which are on the stack do not have a "next greater" element. For all these elements we add mappings from the element to -1.

[3,1,2,4,5,0]

i : 4
nums2[i] : end
stack : empty
map : (1 -> 2), (2 -> 4), (3 -> 4), (4 -> 5), (0 -> -1), (5 -> -1)

Now, all that needs to be done is to populate the output array with the next greater elements of nums1.

nums1: [3,4,0]
map : (1 -> 2), (2 -> 4), (3 -> 4), (4 -> 5), (0 -> -1), (5 -> -1)
ans : []

The first element 3 maps to 4, 4 maps to 5 and 0 maps to -1. So the output array would be:

ans: [4,5,-1]

Here, m is the length of nums1 and n is the length of nums2.

• Time complexity: O(m+n)

Time complexity is O(m+n) because we iterate through nums2 once to create mappings to the next greater element and we iterate through nums1 to populate the output array. In the worst case we pop all the elements of the stack at once, but that only requires a total of n operations so total number of operations is 2n, n operations to iterate through nums2 and n operations to pop elements off the stack and create mappings. It reduces to O(n). Then to populate the output array requires O(m) operations to iterate through nums1, giving us total complexity of O(m+n).

• Space complexity: O(n)

Space Complexity is O(n) because our HashMap will store mappings to the n elements. The size of the output array does not matter in calculating the space complexity.

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n                     = nums1.length;
        int m                     = nums2.length;
        Stack<Integer> s          = new Stack<>();
        Map<Integer,Integer> next = new HashMap<>();
        int[] ans                 = new int[n];

        for (int i = 0; i < m; i++) {
            while (!s.isEmpty() && s.peek() < nums2[i]) {
                int num = s.peek();
                next.put(num, nums2[i]);
                s.pop();
            }
            s.push(nums2[i]);
        }

        while (!s.isEmpty()) {
            int num = s.pop();
            next.put(num, -1);
        }

        for (int i = 0; i < n; i++) {
            ans[i] = next.get(nums1[i]);
        }

        return ans;
    }
}